package leetcode.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2021/12/5 下午3:58
 */
public class _144前序遍历 {

    public static List<Integer> preorderRecruse(TreeNode root) {
        List<Integer>result=new ArrayList<>();
        if (root==null){
            return  result;
        }
        doPreOrder(result,root);
        return  result;
    }

    private static void doPreOrder(List<Integer> result, TreeNode root) {
        if (root==null){
            return;
        }
        result.add(root.val);
        doPreOrder(result,root.left);
        doPreOrder(result,root.right);
    }

    /**
     * 迭代 前序遍历
     * @param root
     * @return
     */
    public static List<Integer> preorderIterate(TreeNode root) {
        List<Integer> ans =new ArrayList();
        if (root == null){
            return ans;
        }
        Deque<TreeNode> stack=new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur= stack.pop();
            ans.add(cur.val);
            if(cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left !=null ){
                stack.push(cur.left);
            }
        }
        return ans;

    }

    /**
     * morris 解决后序遍历 morris 的核心思想是找到当前遍历顺序的前驱节点，对于后序遍历，某个节点的前驱节点
     *
     * @param root
     * @return
     */
    public static List<Integer> preorderMorris(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        TreeNode current=root;
        TreeNode pre =null;
        while (current!=null){
            pre=current.left;
            if (pre==null){
                result.add(current.val);
                current=current.right;
                continue;
            }
            while (pre.right!=null && pre.right!=current){
                pre = pre.right;
            }
            if (pre.right==null){
                pre.right=current;
                result.add(current.val);
                current=current.left;
            }else {
                pre.right=null;
                current=current.right;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        /*
              0
           1    2
              3    4
         */
        TreeNode treeNode = new TreeNode(0);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(2);
        treeNode.right.left = new TreeNode(3);
        treeNode.right.right = new TreeNode(4);
        List<Integer> list = preorderIterate(treeNode);
        System.out.println(list);
    }
}
